package com.company.test27_28;

import java.util.List;

/**
 * Created by Administrator on 2016.11.8.
 */
public class UnweightedGraph<V> extends AbstractGraph<V>{
    public UnweightedGraph(int[][] edges,V[] vertices){
        super(edges,vertices);
    }

    public UnweightedGraph(List<Edge> edges,List<V> vertices){
        super(edges,vertices);
    }

    public UnweightedGraph(int[][] edges,int numberOfVertices){
        super(edges,numberOfVertices);
    }

    public UnweightedGraph(List<Edge> edges,int numberOfVertices){
        super(edges,numberOfVertices);
    }

    public UnweightedGraph(List<Edge> edges,V[] vertices){
        super(edges,vertices);
    }

    public UnweightedGraph(int[][] edges,List<V> vertices){
        super(edges,vertices);
    }

    public static void main(String[] args) {
        String[] vertices={"Seattle","San Francisco","Los Angeles","Denver",
                "Kansas City","Chicago","Boston","New York",
                "Atlanta","Miami","Dallas","Houston"};

        int[][] edges={
                {0,1},{0,3},{0,5},
                {1,0},{1,2},{1,3},
                {2,1},{2,3},{2,4},{2,10},
                {3,0},{3,1},{3,2},{3,4},{3,5},
                {4,2},{4,3},{4,5},{4,7},{4,8},{4,10},
                {5,0},{5,3},{5,4},{5,6},{5,7},
                {6,5},{6,7},
                {7,4},{7,5},{7,6},{7,8},
                {8,4},{8,7},{8,9},{8,10},{8,11},
                {9,8},{9,11},
                {10,2},{10,4},{10,8},{10,11},
                {11,8},{11,9},{11,10}
        };

        Graph<String> graph=new UnweightedGraph<String>(edges,vertices);
        Graph.SpanningTree bfsTree= graph.bfs(5);
        //Graph.SpanningTree dfsTree= graph.dfs(5);
        List<Integer> searchOrders=bfsTree.getSearchOrders();

        System.out.println(bfsTree.getNumberOfVerticesFound()+
        "vertices are searched in this DFS order:");

        for(int i=0;i<searchOrders.size();i++){
            System.out.println(graph.getVertex(searchOrders.get(i))+" ");
        }
        System.out.println();

        for(int i=0;i<searchOrders.size();i++){
            if(bfsTree.getParent(i)!=-1)
                System.out.println("parent of "+graph.getVertex(i)+" is "+
                graph.getVertex(bfsTree.getParent(i)));
        }
        List list=graph.getHamiltonianPath("Seattle");
        for(int i=0;i<list.size();i++){
            System.out.println(list.get(i));
        }
    }
}
